package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

import java.util.*;

public class _16_Solution {

    public List<Integer> largestDivisibleSubset(int[] nums) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            LinkedList<Integer> list = new LinkedList<>();
            list.add(nums[i]);
            map.put(i,list);
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    if (nums[i] % nums[j] == 0) {
                        List<Integer> integers = map.get(i);
                        if (integers.isEmpty()) {
                            integers.add(nums[j]);
                        } else {
                            boolean flag = true;
                            for (Integer integer : integers) {
                                if (integer > nums[j]) {
                                    if (integer % nums[j] != 0) {
                                        flag = false;
                                        break;
                                    }
                                } else {
                                    if (nums[j] % integer != 0) {
                                        flag = false;
                                        break;
                                    }
                                }
                            }
                            if (flag) {
                                integers.add(nums[j]);
                            }
                        }
                    }
                } else {
                    if (nums[j] % nums[i] == 0) {
                        List<Integer> integers = map.get(i);
                        if (integers.isEmpty()) {
                            integers.add(nums[j]);
                        } else {
                            boolean flag = true;
                            for (Integer integer : integers) {
                                if (integer > nums[j]) {
                                    if (integer % nums[j] != 0) {
                                        flag = false;
                                        break;
                                    }
                                } else {
                                    if (nums[j] % integer != 0) {
                                        flag = false;
                                        break;
                                    }
                                }
                            }
                            if (flag) {
                                integers.add(nums[j]);
                            }
                        }
                    }
                }
            }
        }
        List<Integer> result = map.get(0);
        for (int i = 1; i < map.size(); i++) {
            if (map.get(i).size() > result.size()) {
                result = map.get(i);
            }
        }
        return result;
    }

    public List<Integer> largestDivisibleSubset2(int[] nums){
        Arrays.sort(nums);
        int[] dpCnt = new int[nums.length];
        int[] dpInd = new int[nums.length];
        Arrays.fill(dpInd,-1);
        int maxIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (dpCnt[j] > dpCnt[i]) {
                        dpCnt[i] = dpCnt[j];
                        dpInd[i] = j;
                    }
                }
            }
            dpCnt[i]++;
            if (dpCnt[i] > dpCnt[maxIndex]) {
                maxIndex = i;
            }
        }
        ArrayList<Integer> result = new ArrayList<>();
        while (maxIndex != -1) {
            result.add(nums[maxIndex]);
            maxIndex = dpInd[maxIndex];
        }
        return result;
    }

    @Test
    public void test(){
        int[] nums = {5,9,18,54,108,540,90,180,360,720};
        System.out.println(Arrays.toString(largestDivisibleSubset2(nums).toArray()));
    }
}
